﻿using System;
using System.Collections.Generic;
using System.Text;

namespace ExpressionCompute
{
    public class Program
    {
        /// <summary>
        /// 主入口方法
        /// </summary>
        /// <param name="args">命令行参数</param>
        static void Main(string[] args)
        {
            // 获得用户输入
            string Input = " 3 + 2 * 4";
            try
            {
                // 计算值
                double result = Compute(Input);
                Console.WriteLine($"计算结果: {result}");
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

        /// <summary>
        /// 计算四则运算表达式
        /// </summary>
        /// <param name="Input">输入的表达式字符串</param>
        /// <returns>表达式的计算结果</returns>
        public static double Compute(string Input)
        {
            // 分解元素 => 队列 list
            var tokens = DataClean(Input);

            // 中缀 => 逆波兰
            var rpn = MidToPRn(tokens);

            // 逆波兰 => 值
            double value = PRNCompute(rpn);
            return value;
        }

        /// <summary>
        /// 分解元素 => 队列 list
        /// </summary>
        /// <param name="Input">输入的表达式字符串</param>
        /// <returns>包含表达式元素的列表</returns>
        public static List<string> DataClean(string Input)
        {
            int i = 0;
            List<string> list = new List<string>();
            while (i < Input.Length)
            {
                // ch为当前字符
                var ch = Input[i];
                if (IsDigit(ch))
                {
                    // 当前位数字
                    StringBuilder sb = new StringBuilder();
                    while (IsDigit(ch))
                    {
                        sb.Append(ch);
                        i++;
                        if (i == Input.Length) break;
                        ch = Input[i];
                    }
                    list.Add(sb.ToString());
                    i--; // 回退一步，因为for循环还会再加1
                }
                else if (IsOperator(ch) || ch == '(' || ch == ')')
                {
                    // 当前为操作符或括号
                    // 将当前操作符或括号压入结果队列
                    list.Add(ch.ToString());
                }
                else if (ch == ' ')
                {
                    // 当前为空格
                    // 空格舍弃不处理
                }
            
                i++;
            }

            return list;
        }

        /// <summary>
        /// 中缀 => 逆波兰
        /// </summary>
        /// <param name="Input">包含中缀表达式元素的列表</param>
        /// <returns>包含逆波兰表达式元素的队列</returns>
        public static Queue<string> MidToPRn(List<string> Input)
        {
            Stack<string> opStack = new Stack<string>(); // 操作符栈
            Queue<string> outputQueue = new Queue<string>(); // 输出队列

            foreach (var token in Input)
            {
                if (IsDigit(token)) // 如果是数字，则直接加入输出队列
                {
                    outputQueue.Enqueue(token);
                }
                else if (IsOperator(token)) // 如果是运算符
                {
                    // 将栈顶优先级大于等于当前运算符的运算符弹出并加入输出队列
                    while (opStack.Count > 0 && Precedence(opStack.Peek()) >= Precedence(token))
                    {
                        outputQueue.Enqueue(opStack.Pop());
                    }
                    opStack.Push(token); // 当前运算符压入栈
                }
                else if (token == "(") // 如果是左括号，则压入栈中
                {
                    opStack.Push(token);
                }
                else if (token == ")") // 如果是右括号
                {
                    // 弹出栈中的运算符并加入输出队列，直到遇到左括号
                    while (opStack.Count > 0 && opStack.Peek() != "(")
                    {
                        outputQueue.Enqueue(opStack.Pop());
                    }
                    if (opStack.Count == 0)
                    {
                        throw new Exception("括号不匹配");
                    }
                    opStack.Pop(); // 弹出左括号
                }
            }

            // 将栈中剩余的运算符弹出并加入输出队列
            while (opStack.Count > 0)
            {
                var op = opStack.Pop();
                if (op == "(")
                {
                    throw new Exception("括号不匹配");
                }
                outputQueue.Enqueue(op);
            }

            return outputQueue;
        }

        /// <summary>
        /// 逆波兰 => 值
        /// </summary>
        /// <param name="Input">包含逆波兰表达式元素的队列</param>
        /// <returns>表达式的计算结果</returns>
        public static double PRNCompute(Queue<string> Input)
        {
            Stack<double> stack = new Stack<double>(); // 数字栈

            while (Input.Count > 0)
            {
                var token = Input.Dequeue();

                if (IsDigit(token))
                {
                    // 如果是数字，压入栈中
                    stack.Push(double.Parse(token));
                }
                else if (IsOperator(token))
                {
                    // 如果是运算符，弹出两个数字进行计算，然后将结果压入栈中
                    double b = stack.Pop();
                    double a = stack.Pop();
                    switch (token)
                    {
                        case "+":
                            stack.Push(a + b);
                            break;
                        case "-":
                            stack.Push(a - b);
                            break;
                        case "*":
                            stack.Push(a * b);
                            break;
                        case "/":
                            stack.Push(a / b);
                            break;
                    }
                }
            }

            // 栈中剩下的唯一元素即为计算结果
            return stack.Pop();
        }

        /// <summary>
        /// 判断字符是否为数字或小数点
        /// </summary>
        /// <param name="ch">待判断的字符</param>
        /// <returns>如果是数字或小数点返回true，否则返回false</returns>
        private static bool IsDigit(char ch)
        {
            return (ch >= '0' && ch <= '9') || ch == '.';
        }

        /// <summary>
        /// 判断字符串是否为数字
        /// </summary>
        /// <param name="str">待判断的字符串</param>
        /// <returns>如果是数字返回true，否则返回false</returns>
        private static bool IsDigit(string str)
        {
            if (string.IsNullOrEmpty(str)) return false;
            foreach (char c in str)
            {
                if (!IsDigit(c)) return false;
            }
            return true;
        }

        /// <summary>
        /// 判断字符是否为操作符
        /// </summary>
        /// <param name="ch">待判断的字符</param>
        /// <returns>如果是操作符返回true，否则返回false</returns>
        private static bool IsOperator(char ch)
        {
            return "+-*/".Contains(ch);
        }

        /// <summary>
        /// 判断字符串是否为操作符
        /// </summary>
        /// <param name="str">待判断的字符串</param>
        /// <returns>如果是操作符返回true，否则返回false</returns>
        private static bool IsOperator(string str)
        {
            return str.Length == 1 && IsOperator(str[0]);
        }

        /// <summary>
        /// 获取运算符的优先级
        /// </summary>
        /// <param name="op">运算符</param>
        /// <returns>运算符的优先级，如果不是有效运算符返回-1</returns>
        private static int Precedence(string op)
        {
            switch (op)
            {
                case "+":
                case "-":
                    return 1;
                case "*":
                case "/":
                    return 2;
                default:
                    return -1;
            }
        }
    }
}